When we try to solve Multiobjective Optimization Problems (MOPs) using an evolutionary algorithm, the Pareto Genetic Algorithm (Pareto GA) introduced by Goldberg in 1989 has now become a sort of standard. After the first introduction, this approach was further developed and lead to many applications. All of these approaches are based on Pareto ranking and use the fitness sharing function to maintain diversity. On the other hand in the early 50's another scheme was presented by Nash. This approach introduced the notion of Nash Equilibrium and aimed at solving optimization problems having multiobjective functions that are originated from Game Theory and Economics. Since the concept of Nash Equilibrium as a solution of these problems was introduced, game theorists have attempted to formalize aspects of the equilibrium solution. The Nash Genetic Algorithm (Nash GA), which is introduced by Sefrioui, is the idea to bring together genetic algorithms and Nash strategy. The aim of this algorithm is to find the Nash Equilibrium of MOPs through the genetic process. Another central achievement of evolutionary game theory is the introduction of a method by which agents can play optimal strategies in the absence of rationality. Not the rationality but through the process of Darwinian selection, a population of agents can evolve to an Evolutionary Stable Strategy (ESS) introduced by Maynard Smith in 1982. In this paper, we propose Game theory based Co-Evolutionary Algorithm (GCEA) and try to find the ESS as a solution of MOPs. By applying newly designed co-evolutionary algorithm to several MOPs, the first we will confirm that evolutionary game can be embodied by co-evolutionary algorithm and this co-evolutionary algorithm can find ESSs as a solutions of MOPs. The second, we show optimization performance of GCEA by applying this model to several test MOPs and comparing with the solutions of previously introduced evolutionary optimization algorithms.

In this paper, performance of chaos and burst noises injected to the Hopfield Neural Network for quadratic assignment problems is investigated. For the evaluation of the noises, two methods to appreciate finding a lot of nearly optimal solutions are proposed. By computer simulations, it is confirmed that the burst noise generated by the Gilbert model with a laminar part and a burst part achieved the good performance as the intermittency chaos noise near the three-periodic window.

Edge linking is a fundamental computer vision task, yet presents difficulties arising from the lack of information in the image. Viewed as a constrained optimization problem, it is NP hard-being isomorphic to the classical Traveling Salesman Problem. This paper proposes a gradient ascent learning algorithm of the elastic net approach for edge linking of images. The learning algorithm has two phases: an elastic net phase, and a gradient ascent phase. The elastic net phase minimizes the path through the edge points. The procedure is equivalent to gradient descent of an energy function, and leads to a local minimum of energy that represents a good solution to the problem. Once the elastic net gets stuck in local minima, the gradient ascent phase attempts to fill up the valley by modifying parameters in a gradient ascent direction of the energy function. Thus, these two phases are repeated until the elastic net gets out of local minima and produces the shortest or better contour through edge points. We test the algorithm on a set of artificial images devised with the aim of demonstrating the sort of features that may occur in real images. For all problems, the systems are shown to be capable of escaping from the elastic net local minima and producing more meaningful contours than the original elastic net.

Analog Hopfield neural networks (HNNs) have so far been used to solve many kinds of optimization problems, in particular, combinatorial problems such as the TSP, which can be described by an objective function and some equality constraints. When we solve a minimization problem with equality constraints by using HNNs, however, the constraints are satisfied only approximately. In this paper we propose a circuit which rigorously realizes the equality constraints and whose energy function corresponds to the prescribed objective function. We use the SPICE program to solve circuit equations corresponding to the above circuits. The proposed method is applied to several kinds of optimization problems and the results are very satisfactory.

In a previous study about a combinatorial optimization problem solver using neural networks, since the Hopfield method, convergence to the optimum solution sooner and with more certainty is regarded as important. Namely, only static states are considered as the information. However, from a biological point of view, dynamical systems have attracted attention recently. Therefore, we propose a "dynamical" combinatorial optimization problem solver using hysteresis neural networks. In this paper, the proposed system is evaluated by the N-Queen problem.

This paper proposes a gradient ascent learning algorithm for the elastic net approach to the Traveling Salesman Problem (TSP). The learning model has two phases: an elastic net phase, and a gradient ascent phase. The elastic net phase is equivalent to gradient descent of an energy function, and leads to a local minimum of energy that represents a good solution to the problem. Once the elastic net gets stuck in local minima, the gradient ascent phase attempts to fill up the valley by modifying parameters in a gradient ascent direction of the energy function. Thus, these two phases are iterated until the elastic net gets out of local minima. We test the algorithm on many randomly generated travel salesman problems up to 100 cities. For all problems, the systems are shown to be capable of escaping from the elastic net local minima and generating shorter tour than the original elastic net.

When solving combinatorial optimization problems with a binary Hopfield-type neural network, the updating process in neural network is an important step in achieving a solution. In this letter, we propose a new updating procedure in binary Hopfield-type neural network for efficiently solving combinatorial optimization problems. In the new updating procedure, once the neuron is in excitatory state, then its input potential is in positive saturation where the input potential can only be reduced but cannot be increased, and once the neuron is in inhibitory state, then its input potential is in negative saturation where the input potential can only be increased but cannot be reduced. The new updating procedure is evaluated and compared with the original procedure and other improved methods through simulations based on N-Queens problem. The results show that the new updating procedure improves the searching capability of neural networks with shorter computation time. Particularly, the simulation results show that the performance of proposed method surpasses the exiting methods for N-queens problem in synchronous parallel computation model.

We propose hysteresis neural network solving combinatorial optimization problems, Box Puzzling Problem. Hysteresis neural network searches solutions of the problem with nonlinear dynamics. The output vector becomes stable only when it corresponds with a solution. This system does never become stable without satisfying constraints of the problem. After estimating hardware calculating time, we obtain that numerical calculating time increases extremely comparing with hardware time as problem's scale increases. However the system has possibility of limit cycle. Though it is very hard to remove limit cycle completely, we propose some methods to remove this phenomenon.

This paper proposes aspiration controls which restrains aspiration branches and keeps the original tabu-based searching by considering past and/or (predicted) future searching profiles. For implementation of the aspiration control we employ not only the short-term and long-term memory but also future memory which is first introduced in this paper as a new concept in the tabu search field. The tabu search with the aspiration control is also parallelized. Moreover two types of parallel cooperative searching scheme are proposed. Through computational experiment, we observe efficiency of our approach comparing to the traditional ones. Especially, we find that cooperative searching has possibility to improve the solution quality very well.

A WDM (Wavelength Division Multiplexing) technology is a new optical technology, providing multiple wavelengths at the rate of 10 Gbps on the fiber. IP (Internet Protocol) over WDM networks where IP packets are directly carried on the WDM network is expected to offer an infrastructure for the next generation Internet. For IP over WDM networks, a WDM protection mechanism is expected to provide a highly reliable network (i.e., robustness against the link/node failures). However, conventional IP also provides a reliability mechanism by its routing function. In this paper, we first formulate an optimization problem for designing IP over WDM networks with protection functionalities of WDM networks, by which we can obtain IP over WDM networks with high reliability. Our formulation results in a mixed integer linear problem (MILP). However, it is known that MILP can be solved only for a small number of variables, in our case, nodes and/or wavelengths. We therefore propose two heuristic algorithms, min-hop-first and largest-traffic-first approaches in order to assign the wavelength for backup lightpath. Our results show that the min-hop-first approach takes fewer wavelengths to construct the reliable network, that is, all of lightpaths can be protected using the WDM protection mechanism. However, our largest-traffic-first approach is also a good choice in the sense that the approach can be saved the traffic volume increased at the IP router by the link failure.

A constraint resolution scheme in the Hopfield-type neural network named "Neuron Filter" is presented for efficiently solving combinatorial optimization problems. The neuron filter produces an output that satisfies the constraints of the problem as best as possible according to both neuron inputs and outputs. This paper defines the neuron filter and shows its introduction into existing neural networks for N-queens problems and FPGA board-level routing problems. The performance is evaluated through simulations where the results show that our neuron filter improves the searching capability of the neural network with the shorter computation time.

We survey recent developments in the study of approximation algorithms for NP-hard geometric optimization problems. We focus on those problems which, given a set of points, ask for a graph of a specified type on those points with the minimum total edge length, such as the traveling salesman problem, the Steiner minimum tree problem, and the k-minimum spanning tree problem. In a recent few years, several polynomial time approximation schemes are discovered for these problems. All of them are dynamic programming algorithms based on some geometric theorems that assert the existence of a good approximate solution with a simple recursive decomposition structure. Our emphasis is on these geometric theorems, which have potential uses in the design and analysis of heuristic algorithms.

Recently, researchers in various fields have shown interest in the behavior of creatures from the viewpoint of adaptiveness and flexibility. Ants, known as social insects, exhibit collective behavior in performing tasks that can not be carried out by an individual ant. In ant colonies, chemical substances, called pheromones, are used as a way to communicate important information on global behavior. For example, ants looking for food lay the way back to their nest with a specific type of pheromone. Other ants can follow the pheromone trail and find their way to baits efficiently. In 1991, Colorni et al. proposed the ant algorithm for Traveling Salesman Problems (TSPs) by using the analogy of such foraging behavior and pheromone communication. In the ant algorithm, there is a colony consisting of many simple ant agents that continuously visit TSP cities with opinions to prefer subtours connecting near cities and they lay strong pheromones. The ants completing their tours lay pheromones of various intensities with passed subtours according to distances. Namely, subtours in TSP tourns that have the possibility of being better tend to have strong pheromones, so the ant agents specify good regions in the search space by using this positive feedback mechanism. In this paper, we propose a multiple ant colonies algorithm that has been extended from the ant algorithm. This algorithm has several ant colonies for solving a TSP, while the original has only a single ant colony. Moreover, two kinds of pheromone effects, positive and negative pheromone effects, are introduced as the colony-level interactions. As a result of colony-level interactions, the colonies can exchange good schemata for solving a problem and can maintain their own variation in the search process. The proposed algorithm shows better performance than the original algorithm with almost the same agent strategy used in both algorithms except for the introduction of colony-level interactions.

We propose a hysteresis neural network system solving NP-Hard optimization problems, the N-Queens Problem. The continuous system with binary outputs searches a solution of the problem without energy function. The output vector corresponds to a complete solution when the output vector becomes stable. That is, this system does never become stable without satisfying the constraints of the problem. Though it is very hard to remove limit cycle completely from this system, we can propose a new method to reduce the possibility of limit cycle by controlling time constants.

This paper develops an algorithm based on the Modular Approach to solve singly constrained separable discrete optimization problems (Nonlinear Knapsack Problems). The Modular Approach uses fathoming and integration techniques repeatedly. The fathoming reduces the decision space of variables. The integration reduces the number of variables in the problem by combining several variables into one variable. Computational experiments for "hard" test problems with up to 1000 variables are provided. Each variable has up to 1000 integer values.

A novel analog-computation system using quantum-dot spin glass is proposed. Analog computation is a processing method that solves a mathematical problem by applying an analogy of a physical system to the problem. A 2D array of quantum dots is constructed by mixing two-dot (antiferromagnetic interaction) and three-dot (ferromagnetic interaction) systems. The simulation results show that the array shows spin-glass-like behavior. We then mapped two combinatorial optimization problems onto the quantum-dot spin glasses, and found their optimal solutions. The results demonstrate that quantum-dot spin glass can perform analog computation and solve a complex mathematical problem.

In this paper, we propose a new cooperative search algorithm based on pheromone communication for solving the Vehicle Routing Problems. In this algorithm, multi-agents can partition the problem cooperatively and search partial solutions independently using pheromone communication, which mimics the communication method of real ants. Through some computer experiments the cooperative search of multi-agents is confirmed.

The lower-bounded p-collection problem is the problem where to locate p sinks in a flow network with lower bounds such that the value of a maximum flow is maximum. This paper discusses the cover problems corresponding to the lower bounded p-collection problem. We consider the complexity of the cover problem, and we show polynomial time algorithms for its subproblems in a network with tree structure.

In this paper we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the lower-bounded p-collection problem. First we discuss the complexity of this problem to show NP-hardness for a network with path structure. Next we present a linear time algorithm for the lower-bounded 1-collection problem in a network with tree structure, and a pseudo-polynomial time algorithm with dynamic programming type for the lower-bounded p-collection problem in a network with tree structure. Using the pseudo-polynomial time algorithm, we show an exponential algorithm, which is efficient in a connected network with few cycles, for the lower-bounded p-collection problem.

We analyze additive effects of nonlinear dynamics for conbinatorial optimization. We apply chaotic time series as noise sequence to neural networks for 10-city and 20-city traveling salesman problems and compare the performance with stochastic processes, such as Gaussian random numbers, uniform random numbers, 1/fα noise and surrogate data sets which preserve several statistics of the original chaotic data. In result, it is shown that not only chaotic noise but also surrogates with similar autocorrelation as chaotic noise exhibit high solving abilities. It is also suggested that since temporal structure of chaotic noise characterized by autocorrelation affects abilities for combinatorial optimization problems, effects of chaotic sequence as additive noise for escaping from undesirable local minima in case of solving combinatorial optimization problems can be replaced by stochastic noise with similar autocorrelation.